package leetcode.string;

/**
 * @Description: https://leetcode.cn/problems/reverse-words-in-a-string/
 * @Author Ammar
 * @Create 2023/7/13 17:50
 */
public class _151_反转字符串中的单词 {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return "";
        char[] sChars = s.toCharArray();
        // 去除字符串中的空格 包括单词间的
        // [ , , a, b, c, , o, k] => [a, b, c, , o, k, , ,]
        int len = 0; // 最终字符串的有效长度
        int end = 0;
        boolean space = true; // 前一个数是否为空格，默认第一个字符为空格
        for (int i = 0; i < sChars.length; i++) {
            if (sChars[i] != ' ') {
                sChars[end++] = sChars[i];
                space = false;
            } else if (space == false) {
                // 前一个为非空格，下一个为空格
                sChars[end++] = ' ';
                space = true;
            }
        }
        len = space ? end - 1 : end;
        if (len <= 0) return "";

        // [a, b, c, , o, k, , ] => [k, o, , a, b, c, , ]
        // len 到 c
        reverse(sChars, 0, len);
        // 将每个单词进行翻转
        int prevIndexIsSpace = -1;
        for (int i = 0; i < len; i++) {
            if (sChars[i] == ' ') {
                reverse(sChars, prevIndexIsSpace + 1, i);
                prevIndexIsSpace = i;
            }
        }
        // 翻转最后一个单词
        reverse(sChars, prevIndexIsSpace + 1, len);
        return new String(sChars, 0, len);
    }

    public void reverse(char[] s, int start, int end) {
        end--;
        while (start < end) {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start++;
            end--;
        }
    }

}
